package com.zj.base;

/**
 * @program algorithm
 * @description:
 * @author: zhangbo
 * @create: 2022/08/28 23:47
 */
public class MergeSort04 {


    /**
     * 归并算法，再记住，这是双指针，双指针！！！记住双指针！，明天再开一遍，双指针
     *
     * @param arr
     * @param left
     * @param mid
     * @param right
     */
    public void merge(int[] arr, int left, int mid, int right) {

        int[] temp = new int[(right - left) / 2 + left];

        int l = left;

        int r = mid + 1;

        int i = 0;

        while (l <= mid && r <= right) {
            if (arr[l] <= arr[mid]) {
                temp[i++] = temp[l++];
            } else {
                temp[i++] = temp[r++];
            }

        }

        while (l <= mid) {
            temp[i++] = temp[l++];
        }

        while (r <= right) {
            temp[i++] = temp[r++];
        }

        for (int j = 0; j < temp.length; j++) {
            arr[left + j] = temp[j];
        }
    }

    public void sort(int[] arr, int left, int right) {
        int mid = (right - left) / 2 - left;
        if (left < right) {
            sort(arr, left, mid);
            sort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
}
